package 算法;

// 环形单链表的约瑟夫环问题，时间复杂度是O（m*n）,另一种方法是找规律
//双指针last指向末尾，head指向当前指针
public class JosephusKill {
    public Node josephusKill(Node head,int m){
        if(head==null || head.next==head || m<1){
            return head;
        }
        Node last = head;
        while(last.next!=head){
            last = last.next;
        }
        int count=0;
        while(head!=last){
            if(++count==m){
                last.next = head.next;
                count = 0;
            }else{
                last = last.next;
            }
            head = head.next;
        }
        return head;

    }

}

class Node{
    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }
}
